\begin{frame}
\frametitle{Cellular Automata}

\begin{define}[2DOTA, 2OTA~\cite{Giammarresi1997}]

A deterministic two-dimensional online tesselation automaton is a
5-tuple $M~=~(Z,~\Sigma,~\delta,~z_0,~E)$, where

\begin{itemize}
	\item Z is a finite set of states
	\item $\Sigma$ is a finite set of input symbols
	\item $z_0~\in~Z$ is the set of initial states
	\item E~$\subseteq$~Z is the set of accepting states
	\item $\delta:~Z~\times~Z~\times~\Sigma~\rightarrow~Z$ is the control
		function
\end{itemize}

\end{define}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example}

\begin{example}
$M~=~(\{z_0, z_1, z_2, z_e\}, \{0\}, \delta, \{z_0\}, \{z_e\})$

$\delta(z_e, z_0, 0) = \delta(z_1, z_0, 0) = \delta(z_e, z_1, 0) = \delta(z_1,
z_1, 0) = z_1$\\
$\delta(z_0, z_e, 0) = \delta(z_0, z_2, 0) = \delta(z_2, z_e, 0) = \delta(z_2,
z_2, 0) = z_2$\\
$\delta(z_0, z_0, 0) = \delta(z_2, z_1, 0) = z_e$\\
\end{example}

$L = \{p\mid p\in\Sigma^{**},~l_1(p)~=~l_2(p)\}$ is the language of all
quadratic pictures.

\begin{align*}
L(M) &= \{p \in \Sigma^{**}\mid \text{p is accepted by M}\}\\
L(M) &= L
\end{align*}

\end{frame}

\begin{frame}
\frametitle{Closure Properties}

\begin{thm}[Theorem 4.5, 4.6~\cite{Giammarresi1997}]
$\mathcal{L}(2OTA)$ is closed under projection, concatenation and closure
operations.
\end{thm}

\begin{proof}
Let $\Sigma$ and $\Gamma$ be two finite alphabets and let $\pi: \Gamma
\rightarrow \Sigma$ be a projection. Let $L \subseteq \Gamma^{**}$ be a language
recognized by a 2OTA $M = (\Gamma, Q, I, F, \delta)$. Then, it is easy
to verify that language $L' = \pi(L)$ is recognized by the 2OTA $M' =
(\Sigma, Q, I, F, \delta')$ where: 
\begin{align*}
\delta'(p, q, a) = \bigcup_{b\in\Gamma:\pi(a)=b} \delta(p, q, b)
\end{align*}
\end{proof}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Language hierarchy}

\begin{thm}[Theorem 4.1~\cite{Giammarresi1997}]
$\mathcal{L}(2DOTA)\subset\mathcal{L}(2OTA)$
\end{thm}

\begin{thm}[Theorem 4.1~\cite{Giammarresi1997}]
$co-\mathcal{L}(AFA)\subseteq\mathcal{L}(2OTA)$
\end{thm}

\begin{thm}[Theorem 4.7~\cite{Giammarresi1997}]
$\mathcal{L}(NFA)\subset\mathcal{L}(2OTA)$, \\
$\mathcal{L}(DFA)\not\subset\mathcal{L}(2DOTA)$ and \\
$\mathcal{L}(2DOTA)\not\subset\mathcal{L}(DFA)$.
\end{thm}

\begin{col}[Corollary 4.2~\cite{Ito1997}]
$\mathcal{L}(X)\not\subset\mathcal{L}(2OTA)$ and
$\mathcal{L}(2OTA)\not\subset\mathcal{L}(X)$,
for~$X~=~\{$UFA,~AFA,~DMA(1),~NMA(1),~UMA(1)\}
\end{col}

It is conjectured that $\mathcal{L}(2OTA)$ and $\mathcal{L}(AMA(1))$ are also
incomparable to each other, since if
$\mathcal{L}(2OTA)\subseteq\mathcal{L}(AMA(1))$ were true, then it would be the
case that nondeterministic and deterministic polynomial time complexity classes
are coinsident(i.e. $P = NP$).(~Remark 4.1~\cite{Ito1997})


\end{frame}